/*
 * @lc app=leetcode.cn id=400 lang=cpp
 *
 * [400] 第 N 位数字
 *
 * https://leetcode.cn/problems/nth-digit/description/
 *
 * algorithms
 * Medium (45.55%)
 * Likes:    330
 * Dislikes: 0
 * Total Accepted:    50.4K
 * Total Submissions: 110.5K
 * Testcase Example:  '3'
 *
 * 给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n
 * 位上的数字。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：n = 3
 * 输出：3
 *
 *
 * 示例 2：
 *
 *
 * 输入：n = 11
 * 输出：0
 * 解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= n <= 2^31 - 1
 *
 *
 */

// @lc code=start
#include <iostream>
using namespace std;
class Solution {
public:
    int findNthDigit(int n) {
        if (n == 0) {
            return n;
        }
        // 找到第n位的数字的位数width
        int width = 1;
        while (n > (width * 9 * pow(10, width - 1))) {
            n -= (width * 9 * pow(10, width - 1));
            ++width;
        }
        // index为在该数位等级的第几个数字
        // pos为在该数字的第几位
        int index = n / width;
        int pos = n % width;
        int ans = -1;
        int targetNum = pow(10, width - 1) + index;
        if (pos == 0) {
            targetNum -= 1;
            pos = width;
        }
        cout << "targetNum = " << targetNum << endl;
        cout << "pos = " << pos << endl;
        while (width != pos - 1) {
            ans = targetNum % 10;
            targetNum /= 10;
            --width;
        }
        return ans;
    }
};
// @lc code=end
